{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Top K Frequent Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #divide-and-conquer #bucket-sort #counting #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #分治 #桶排序 #计数 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: topKFrequent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #前 K 个高频元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，请你返回其中出现频率前 <code>k</code> 高的元素。你可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = [1,1,1,2,2,3], k = 2\n",
    "<strong>输出: </strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = [1], k = 1\n",
    "<strong>输出: </strong>[1]</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>k</code> 的取值范围是 <code>[1, 数组中不相同的元素的个数]</code></li>\n",
    "\t<li>题目数据保证答案唯一，换句话说，数组中前 <code>k</code> 个高频元素的集合是唯一的</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你所设计算法的时间复杂度 <strong>必须</strong> 优于 <code>O(n log n)</code> ，其中 <code>n</code><em> </em>是数组大小。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [top-k-frequent-elements](https://leetcode.cn/problems/top-k-frequent-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [top-k-frequent-elements](https://leetcode.cn/problems/top-k-frequent-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,2,2,3]\\n2', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        eles, counts = numpy.unique(numpy.array(nums), return_counts = True)\n",
    "        topk_index = numpy.argsort(counts)[len(counts)-k:]\n",
    "        return eles[list(topk_index)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        memo = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in memo:\n",
    "                memo[nums[i]] += 1\n",
    "            else:\n",
    "                memo[nums[i]] = 1\n",
    "            \n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            max_ele = max(memo, key=memo.get)\n",
    "            res.append(max_ele)\n",
    "            del memo[max_ele]\n",
    "            \n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        s=[]\n",
    "        m=Counter(nums)\n",
    "        a=sorted(m.items(),key=operator.itemgetter(1),reverse=True)\n",
    "        #print(a)\n",
    "        for i,j in a:\n",
    "            s.append(i)\n",
    "            k-=1\n",
    "            if k==0:\n",
    "                break\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        d = dict()\n",
    "        for i in range(len(nums)):\n",
    "            d[nums[i]] = d.get(nums[i],0)+1\n",
    "        l = [0]*(len(nums)+1)\n",
    "        for i in d:\n",
    "            if d[i]!=0:\n",
    "                if l[d[i]]==0:\n",
    "                    l[d[i]]=[]\n",
    "                l[d[i]].append(i)\n",
    "        res = []\n",
    "        for i in range(len(l)-1,-1,-1):\n",
    "            if not l[i]:\n",
    "                continue\n",
    "            if len(res)<k :\n",
    "                res.extend(l[i])\n",
    "                if len(res)==k:\n",
    "                    return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        if len(nums) <= 0:\n",
    "            return []\n",
    "        temp_dict = {}\n",
    "        for item in nums:\n",
    "            temp_dict[item] = temp_dict.get(item, 0) + 1\n",
    "        temp_list = [0] * (max(list(temp_dict.values())) + 1)\n",
    "        for key, value in temp_dict.items():\n",
    "            if isinstance(temp_list[value], list):\n",
    "                temp_list[value].append(key)\n",
    "            else:\n",
    "                temp_list[value] = [key]\n",
    "        result = []\n",
    "        for value in reversed(temp_list):\n",
    "            if isinstance(value, list):\n",
    "                if k <= 0:\n",
    "                    break\n",
    "                else:\n",
    "                    if len(value) > k:\n",
    "                        result.extend(value[0:len(value) - k])\n",
    "                        break\n",
    "                    else:\n",
    "                        result.extend(value)\n",
    "                        k -= len(value)\n",
    "        # result = sorted(result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        look={}\n",
    "        wei=['*']*(len(nums)+1)\n",
    "        for num in nums:\n",
    "            look[num]=look.get(num,0)+1\n",
    "        for key,v in look.items():\n",
    "            if wei[v]=='*':\n",
    "                wei[v]=[]\n",
    "            wei[v].append(key)\n",
    "        res=[]\n",
    "        print(wei)\n",
    "        for i in wei[::-1]:\n",
    "            if len(res)>=k:\n",
    "                break\n",
    "            if i!='*':\n",
    "                res+=i\n",
    "                \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        \n",
    "        d={}\n",
    "        res=[]\n",
    "        ans=[]\n",
    "        buckets=[[]for _ in range(len(nums)+1)]\n",
    "        \n",
    "        for num in nums:\n",
    "            d[num]=d.get(num,0)+1\n",
    "        for key in d:\n",
    "            res.append((d[key],key))\n",
    "        for t in res:\n",
    "            freq,key=t\n",
    "            buckets[freq].append(key)\n",
    "        buckets.reverse()\n",
    "        \n",
    "        for item in buckets:\n",
    "            if item and k>0:\n",
    "                while item and k>0:\n",
    "                    ans.append(item.pop())\n",
    "                    k-=1\n",
    "                if k==0:\n",
    "                    return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        counts = collections.Counter(nums)\n",
    "        buckets = [[] for _ in range(len(nums) + 1)]    \n",
    "        for num in counts.keys():\n",
    "            buckets[counts[num]].append(num)\n",
    "        ans = []\n",
    "        for i in range(len(nums), 0, -1):      \n",
    "            ans += buckets[i]      \n",
    "            if len(ans) == k: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        m = {}\n",
    "        for n in nums:\n",
    "            if n in m:\n",
    "                m[n] += 1\n",
    "                continue\n",
    "            m[n] = 1\n",
    "\n",
    "        buckets = [[] for i in range(len(nums))]\n",
    "        for key, val in m.items():\n",
    "            buckets[val - 1].append(key)\n",
    "\n",
    "        res = []\n",
    "        for bucket in buckets[::-1]:\n",
    "            for bucket_num in bucket:\n",
    "                if len(res) == k:\n",
    "                    return res\n",
    "                res.append(bucket_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        return [key for key,value in collections.Counter(nums).most_common(k)]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "#         if nums == []:\n",
    "#             return []\n",
    "#         nums.sort()\n",
    "#         s = set()\n",
    "#         start = 0\n",
    "#         dic = {}\n",
    "#         for i in range(len(nums)):\n",
    "#             s.add(nums[i])\n",
    "        \n",
    "#         s = list(s)\n",
    "#         s.sort()\n",
    "#         for e in s:\n",
    "#             freq = 0\n",
    "#             while start < len(nums) and nums[start] == e:\n",
    "#                 freq += 1\n",
    "#                 start += 1\n",
    "#             dic[e] = freq\n",
    "        \n",
    "#         items = dic.items()\n",
    "#         backitems = [[v[1],v[0]] for v in items]\n",
    "#         backitems.sort()\n",
    "        \n",
    "#         return [k for [f,k] in backitems[len(backitems)-k:]]\n",
    "        count = collections.Counter(nums)   \n",
    "        return heapq.nlargest(k, count.keys(), key=count.get)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: 'List[int]', k: 'int') -> 'List[int]':\n",
    "        if nums == []:\n",
    "            return []\n",
    "        dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in dic:\n",
    "                dic[nums[i]] += 1\n",
    "            else:\n",
    "                dic[nums[i]] = 1\n",
    "        b = [[v[1],v[0]] for v in dic.items()]\n",
    "        b.sort()\n",
    "        \n",
    "        return [k for [f,k] in b[len(b)-k:]]\n",
    "        # count = collections.Counter(nums)   \n",
    "        # return heapq.nlargest(k, count.keys(), key=count.get)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = collections.Counter(nums)\n",
    "        return [a[0] for a in dic.most_common(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic={}\n",
    "        while nums:\n",
    "           i= nums.pop()\n",
    "           if i in dic:\n",
    "               continue\n",
    "           else:\n",
    "                dic[i]=nums.count(i)+1\n",
    "        l=[]\n",
    "    \n",
    "        for zzz in range(k):\n",
    "            max=1\n",
    "            key=1\n",
    "            for j in dic:\n",
    "              if dic[j]>=max:\n",
    "                  max=dic[j]\n",
    "                  key=j\n",
    "            dic.pop(key)\n",
    "            l.append(key)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        result,fre_all = [], []\n",
    "        frequency = 0\n",
    "        n = len(nums)\n",
    "        while nums:\n",
    "            i = 0\n",
    "            while i < len(nums):\n",
    "                if i == 0:\n",
    "                    result.append(nums[i])\n",
    "                    frequency += 1\n",
    "                else:\n",
    "                    if nums[i] != nums[0]:\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    else:\n",
    "                        frequency += 1\n",
    "                        nums.pop(i)\n",
    "                        i -= 1\n",
    "                i += 1\n",
    "            nums.pop(0)\n",
    "            fre_all.append(frequency)\n",
    "            frequency = 0\n",
    "        return self.findk(result, fre_all, k)\n",
    "\n",
    "    def findk(self, nums1, nums2, k):\n",
    "        n = len(nums2)\n",
    "        for i in range(n):\n",
    "            for j in range(1, n-i-1):\n",
    "                if nums2[j] > nums2[j-1]:\n",
    "                    nums2[j], nums2[j-1] = nums2[j-1], nums2[j]\n",
    "                    nums1[j], nums1[j-1] = nums1[j-1], nums1[j]\n",
    "        return nums1[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i not in dic :\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        lst=[]\n",
    "        for element in dic.values():\n",
    "            lst.append(element)\n",
    "        lst.sort(reverse=True)\n",
    "        c=lst[k-1]\n",
    "        lst2=[]\n",
    "        for key,value in dic.items():\n",
    "            if value>=c:\n",
    "                lst2.append(key)\n",
    "        return lst2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        dicList = [(i, dic[i]) for i in dic]\n",
    "\n",
    "        # build a heap\n",
    "        for i in range(k // 2, -1, -1):\n",
    "            self.buildHeap(dicList, i, k)\n",
    "\n",
    "        # adjust the heap\n",
    "        for j in range(k, len(dicList)):\n",
    "            if dicList[j][1] > dicList[0][1]:\n",
    "                dicList[j], dicList[0] = dicList[0], dicList[j]\n",
    "                self.buildHeap(dicList, 0, k)\n",
    "        return [s[0] for s in dicList[:k]]\n",
    "\n",
    "    def buildHeap(self, dicList, start, end):\n",
    "        left = start * 2 + 1\n",
    "        right = left + 1\n",
    "        min_pos = start\n",
    "        if left < end and dicList[left][1] < dicList[start][1]:\n",
    "            min_pos = left\n",
    "        if right < end and dicList[right][1] < dicList[min_pos][1]:\n",
    "            min_pos = right\n",
    "        if min_pos != start:\n",
    "            dicList[min_pos], dicList[start] = dicList[start], dicList[min_pos]\n",
    "            self.buildHeap(dicList, min_pos, end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not nums:\n",
    "            return None\n",
    "        count_dict = {}\n",
    "        for n in nums:\n",
    "            if n in count_dict.keys():\n",
    "                continue\n",
    "            count_dict[n] = {'number':n,'total':nums.count(n)}\n",
    "        count_list = list(count_dict.values())\n",
    "        count_list = sorted(count_list,key=lambda x:x['total'],reverse=True)\n",
    "        ans = []\n",
    "        for count_dict in count_list[:k]:\n",
    "            ans.append(count_dict['number'])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def quick(a):\n",
    "            n = len(a)\n",
    "            if n <= 1:\n",
    "                return a\n",
    "            cur, p1, p2 = 0, 0, n - 1\n",
    "#             p1 位置比cur 小 ， p2 >=cur \n",
    "            while p1 < p2:\n",
    "                while p1 <= p2 and a[cur][1] <= a[p1][1]:\n",
    "                    p1 += 1\n",
    "                while a[cur][1] > a[p2][1]:\n",
    "                    p2 -= 1\n",
    "                if p1 < p2:\n",
    "                    a[p1], a[p2] = a[p2], a[p1]\n",
    "            a[cur], a[p2] = a[p2], a[cur]\n",
    "            return quick(a[:p2]) + [a[p2]] + quick(a[p1:])\n",
    "        counter = collections.Counter(nums)\n",
    "        nums = [ele for ele in counter.items()]\n",
    "\n",
    "        res = quick(nums)\n",
    "        return [ele[0] for ele in res[:k]]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        while len(set(nums)) > k:\n",
    "            for num in set(nums):\n",
    "                nums.remove(num)\n",
    "        return list(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        while len(set(nums)) > k:\n",
    "            for num in set(nums):\n",
    "                nums.remove(num)\n",
    "        return list(set(nums))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        mp=dict(collections.Counter(nums))\n",
    "        mp=sorted(mp, key=lambda x: mp[x], reverse=True)\n",
    "        ans=[i for i in mp]\n",
    "        ans=ans[:k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        if(k == len(nums)):\n",
    "            return nums\n",
    "        nums_dict = defaultdict(int)\n",
    "        for item in nums:\n",
    "            nums_dict[item] += 1\n",
    "        topk = [[0,0] for i in range(k)]\n",
    "        heapq.heapify(topk)\n",
    "        for k,v in nums_dict.items():\n",
    "            if topk[0][0] < v:\n",
    "                heapq.heappop(topk)\n",
    "                heapq.heappush(topk,[v,k])\n",
    "        ret = [item[1] for item in topk]\n",
    "        return ret \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        coun = collections.Counter(nums)\n",
    "        res = []\n",
    "        orderd_coun = sorted(coun.items(), key=lambda x:x[1],reverse=True)\n",
    "        j = 0\n",
    "        for i in range(k):\n",
    "            res.append(orderd_coun[j][0])\n",
    "            j+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        # cnt=Counter(nums)\n",
    "        # print(cnt)\n",
    "        # if len(nums)==k: return nums\n",
    "        ans=[]\n",
    "        dic={}\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else: dic[i]=1\n",
    "        # print(dic)\n",
    "        hp=[]\n",
    "#堆排序\n",
    "        for key,v in dic.items():\n",
    "            heapq.heappush(hp,(v,key))\n",
    "            while len(hp) > k:\n",
    "                heapq.heappop(hp)\n",
    "\n",
    "        # for k, v in dic.items():\n",
    "        #     heapq.heappush(hp,(v,k))\n",
    "        #     #最小的在最前面     \n",
    "        #     while len(hp)>k:\n",
    "        #         heapq.heappop(hp)\n",
    "        # print(hp)\n",
    "        for i in hp:\n",
    "            ans.append(i[1])\n",
    "        return ans            \n",
    "        \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        map = {}\n",
    "        for num in nums:\n",
    "            map[num] = map.get(num, 0) + 1\n",
    "        \n",
    "        pri_que = []\n",
    "        for key, freq in map.items():\n",
    "            print(key, freq)\n",
    "            heapq.heappush(pri_que, (freq, key))\n",
    "            if len(pri_que) > k:\n",
    "                heapq.heappop(pri_que)\n",
    "        for key, freq in map.items():\n",
    "            print(key, freq)\n",
    "        ans = [0]*k\n",
    "        for i in range(k-1, -1, -1):\n",
    "            ans[i] = heapq.heappop(pri_que)[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for num in nums:\n",
    "            if num in dic:\n",
    "                dic[num] += 1\n",
    "            else:\n",
    "                dic[num] = 1\n",
    "        # lis = []\n",
    "        # for ch in dic:\n",
    "        #     lis.append((ch,dic[ch]))\n",
    "        # lis = sorted(lis,key=lambda x:-x[1])\n",
    "        # return [lis[i][0] for i in range(k)]\n",
    "        dic = sorted(dic.items(),key=lambda x:x[1],reverse=True)\n",
    "        return [dic[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        res=dict()\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            res[nums[i]]=res.get(nums[i],0)+1\n",
    "\n",
    "        arr=[]\n",
    "\n",
    "        for key,value in res.items():\n",
    "            heapq.heappush(arr,(value,key))\n",
    "            if len(arr)>k:\n",
    "                heapq.heappop(arr)\n",
    "\n",
    "        ans=[0]*k\n",
    "        for i in range(k-1,-1,-1):\n",
    "            ans[i]=heapq.heappop(arr)[1]\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 1. 解法一: 使用最小堆\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        num_count = Counter(nums)\n",
    "        pq = list()\n",
    "        i = 0\n",
    "        for key, val in num_count.items():\n",
    "            if i < k:\n",
    "                heapq.heappush(pq, [val, key])\n",
    "            else:\n",
    "                heapq.heappushpop(pq, [val, key])\n",
    "            i += 1\n",
    "\n",
    "        return [key for _, key in pq]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        fre = {}\n",
    "        for i in nums:\n",
    "            if i in fre:\n",
    "                fre[i] += 1\n",
    "            else:\n",
    "                fre[i] = 1\n",
    "        \n",
    "        keys = list(fre.keys())\n",
    "        keys.sort(key=lambda x: fre[x], reverse=True)\n",
    "        return keys[:k]\n",
    "        # return [i for i, _ in collections.Counter(nums).most_common(k)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "class Solution:\n",
    "    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n",
    "        freq_dic = Counter(nums)\n",
    "        hq = []\n",
    "        for key, val in freq_dic.items():\n",
    "            if len(hq) < k:\n",
    "                heapq.heappush(hq, (val, key))\n",
    "            else:\n",
    "                heapq.heappushpop(hq, (val, key))\n",
    "        res = [ele[1] for ele in hq]\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
